package com.xk._02算法篇._11sequence;

/**
 * @description: KMP算法
 * @author: xu
 * @date: 2022/10/23 23:12
 */
public class KMP {

    // 时间：O(n)
    // 空间：O()
    public static int indexOf(String test, String pattern) {
        if (test == null || pattern == null) return -1;
        char[] testChars = test.toCharArray();
        char[] patternChars = pattern.toCharArray();
        int tlen = testChars.length, plen = patternChars.length;
        if (tlen == 0 || plen == 0 || tlen < plen) return -1;

        // next表
        int[] next = next(pattern);
        int pi = 0, ti = 0, lenDelta = tlen - plen;
        while (pi < plen && (ti - pi) <= lenDelta) {
            if (pi < 0 || testChars[ti] == patternChars[pi]) {
                pi++;
                ti++;
            } else {
                pi = next[pi];
            }
        }
        return pi == plen ? (ti - pi) : -1;
    }

    /**
     * 构建next表 -- 优化
     */
    private static int[] next(String pattern){
        char[] chars = pattern.toCharArray();
        int[] next = new int[chars.length];
        int n = next[0] = -1;
        int i = 0, iMax = chars.length - 1;
        while (i < iMax) {
            if (n < 0 || chars[i] == chars[n]) {
                i++;
                n++;
                if (chars[i] == chars[n]){
                    next[i] = next[n];
                } else {
                    next[i] = n;
                }
            } else {
                n = next[n];
            }
        }
        return next;
    }

    /**
     * 构建next表
     */
    private static int[] next2(String pattern){
        char[] chars = pattern.toCharArray();
        int[] next = new int[chars.length];
        int n = next[0] = -1;
        int i = 0, iMax = chars.length - 1;
        while (i < iMax) {
            if (n < 0 || chars[i] == chars[n]) {
                next[++i] = ++n;
            } else {
                n = next[n];
            }
        }
        return next;
    }
}
